/*------------------------------------------------------------------------
*
* geqo_cx.c
*
*	 循环交叉 [CX] 例程；
*	 根据 Oliver 等人的 CX 操作符
*	 (第二届国际遗传算法会议论文集)
*
* src/backend/optimizer/geqo/geqo_cx.c
*
*-------------------------------------------------------------------------
*/

/* 贡献者：
   =*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=
   *  Martin Utesch				 * 自动控制研究所		   *
   =							 = 矿业与技术大学 =
   *  utesch@aut.tu-freiberg.de  * 德国弗赖贝格				   *
   =*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=
 */

/* cx 算法源自 Genitor： */
/*************************************************************/
/*															 */
/*	Copyright (c) 1990										 */
/*	Darrell L. Whitley										 */
/*	计算机科学系									         */
/*	科罗拉多州立大学									     */
/*															 */
/*	特此允许复制本程序的全部或部分以进行自由分发。作者的姓名  */
/*	及本版权声明必须包含在任何复制中。 */
/* geqo_copy
 *
 *	 将一个基因复制到另一个
 *
 */
/*															 */
/*************************************************************/


#include "postgres.h"
#include "optimizer/geqo_random.h"
#include "optimizer/geqo_recombination.h"

#if defined(CX)

/* cx
 *
 *	 循环交叉
 */
int cx(PlannerInfo *fc_root, Gene *fc_tour1, Gene *fc_tour2, Gene *fc_offspring,
   int fc_num_gene, City * fc_city_table)
{
	int			fc_i,
				fc_start_pos,
				fc_curr_pos;
	int			fc_count = 0;
	int			fc_num_diffs = 0;

	/* 初始化城市表 */
	for (fc_i = 1; fc_i <= fc_num_gene; fc_i++)
	{
		fc_city_table[fc_i].used = 0;
		fc_city_table[fc_tour2[fc_i - 1]].tour2_position = fc_i - 1;
		fc_city_table[fc_tour1[fc_i - 1]].tour1_position = fc_i - 1;
	}

	/* 选择随机周期起始位置 */
	fc_start_pos = geqo_randint(fc_root, fc_num_gene - 1, 0);

	/* 子代继承第一个城市 */
	fc_offspring[fc_start_pos] = fc_tour1[fc_start_pos];

	/* 开始循环与 tour1 */
	fc_curr_pos = fc_start_pos;
	fc_city_table[(int) fc_tour1[fc_start_pos]].used = 1;

	fc_count++;

	/* cx 主要部分 */


/* STEP 1 */

	while (fc_tour2[fc_curr_pos] != fc_tour1[fc_start_pos])
	{
		fc_city_table[(int) fc_tour2[fc_curr_pos]].used = 1;
		fc_curr_pos = fc_city_table[(int) fc_tour2[fc_curr_pos]].tour1_position;
		fc_offspring[fc_curr_pos] = fc_tour1[fc_curr_pos];
		fc_count++;
	}


/* STEP 2 */

	/* 创建完整的旅行失败 */
	if (fc_count < fc_num_gene)
	{
		for (fc_i = 1; fc_i <= fc_num_gene; fc_i++)
		{
			if (!fc_city_table[fc_i].used)
			{
				fc_offspring[fc_city_table[fc_i].tour2_position] =
					fc_tour2[(int) fc_city_table[fc_i].tour2_position];
				fc_count++;
			}
		}
	}


/* STEP 3 */

	/* 仍然无法创建完整的旅行 */
	if (fc_count < fc_num_gene)
	{

		/* 计算母代和子代之间的差异数量 */
		for (fc_i = 0; fc_i < fc_num_gene; fc_i++)
			if (fc_tour1[fc_i] != fc_offspring[fc_i])
				fc_num_diffs++;
	}

	return fc_num_diffs;
}

#endif							/* 定义(CX) */
